function swap(nums, i, j) {
	const temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
}

function bubbleSort(nums) {
	for (let i = 0; i < nums.length - 1; i++) {
		for (let j = 0; j < nums.length - 1 - i; j++) {
			if (nums[j] > nums[j + 1]) swap(nums, j, j + 1);
		}
	}
	return nums;
}

function selectSort(nums) {
	for (let i = 0; i < nums.length - 1; i++) {
		let minIndex = i;
		for (let j = i; j < nums.length; j++) {
			if (nums[j] < nums[minIndex]) minIndex = j;
		}
		swap(nums, i, minIndex);
	}
	return nums;
}

function insertSort(nums) {
	for (let i = 1; i < nums.length; i++) {
		for (let j = i; j - 1 >= 0 && nums[j] < nums[j - 1]; j--) {
			swap(nums, j, j - 1);
		}
	}
	return nums;
}

function shellSort(nums) {
	for (let gap = Math.floor(nums.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
		for (let i = gap; i < nums.length; i++) {
			for (let j = i; j - gap >= 0 && nums[j] < nums[j - gap]; j -= gap) {
				swap(nums, j, j - gap);
			}
		}
	}
	return nums;
}

function quickSort(nums) {
	subSort(nums, 0, nums.length - 1);
	return nums;
}

function subSort(nums, start, end) {
	if (start > end) return;
	let i = start, j = end;
	while (i < j) {
		while (i < j && nums[i] < nums[j]) i++;
		swap(nums, i, j);
		while (i < j && nums[i] <= nums[j]) j--;
		swap(nums, i, j);
	}
	subSort(nums, start, i - 1);
	subSort(nums, i + 1, end);
}

function mergeSort(nums) {
	if (nums.length <= 1) return nums;
	const mid = Math.floor(nums.length / 2);
	const nums1 = mergeSort(nums.slice(0, mid));
	const nums2 = mergeSort(nums.slice(mid));
	return merge(nums1, nums2);
}

function merge(nums1, nums2) {
	let i = 0, j = 0;
	const result = [];
	while (i < nums1.length && j < nums2.length) {
		if (nums1[i] < nums2[j]) result.push(nums1[i++]);
		else result.push(nums2[j++]);
	}
	while (i < nums1.length) result.push(nums1[i++]);
	while (j < nums2.length) result.push(nums2[j++]);
	return result;
}

function heapSort(nums) {
	for (let i = 1; i < nums.length; i++) {
		let child = i;
		let parent = Math.floor((child - 1) / 2);
		while (parent >= 0 && nums[parent] < nums[child]) {
			swap(nums, parent, child);
			child = parent;
			parent = Math.floor((child - 1) / 2);
		}
	}

	for (let i = nums.length - 1; i > 0; i--) {
		swap(nums, 0, i);
		let parent = 0;
		let child = parent * 2 + 1;
		if (child + 1 < i && nums[child + 1] > nums[child]) child++;
		while (child < i && nums[parent] < nums[child]) {
			swap(nums, parent, child);
			parent = child;
			child = parent * 2 + 1;
			if (child + 1 < i && nums[child + 1] > nums[child]) child++;
		}
	}

	return nums;
}

function countSort(nums) {
	const max = Math.max(...nums);
	const buckets = new Array(max + 1).fill(0);
	const result = [];
	nums.forEach((item) => buckets[item]++);
	buckets.forEach((item, index) => {
		while (item--) result.push(index);
	});
	return result;
}

function bucketSort(nums) {
	const min = Math.min(...nums);
	const max = Math.max(...nums);
	const bucketNum = Math.floor((max - min) / 5) + 1;
	const buckets = new Array(bucketNum).fill(0).map(() => []);
	nums.forEach((item) => {
		const index = Math.floor((item - min) / 5);
		buckets[index].push(item);
	});
	const result = [];
	buckets.forEach((bucket) => {
		heapSort(bucket);
		result.push(...bucket);
	});
	return result;
}

function radixSort(nums) {
	const buckets = new Array(10).fill(0).map(() => []);
	const temp = nums.slice();
	const max = Math.max(...nums);
	let base = 1;

	while (base <= max) {
		temp.forEach((item) => {
			const index = Math.floor(item / base) % 10;
			buckets[index].push(item);
		});
		temp.length = 0;
		buckets.forEach((bucket) => {
			temp.push(...bucket);
			bucket.length = 0;
		});
		base *= 10;
	}
	return temp;
}

console.log("bubbleSort", bubbleSort([1, 4, 2, 7, 5, 1, 0, 9, 4]))
console.log("selectSort", selectSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("insertSort", insertSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("shellSort", shellSort([1, 4, 2, 7, 5, 1, -1000, 49935, -4, 777, 0, 9, 1, 4, -30, 0, 9, 4]));
console.log("quickSort", quickSort([1, 4, 2, 7, 5, 1, -1000, 49935, -4, 777, 0, 9, 1, 4, -30, 0, 9, 4]));
console.log("mergeSort", mergeSort([1, 4, 2, 7, 5, 1, -1000, 49935, -4, 777, 0, 9, 1, 4, -30, 0, 9, 4]));
console.log("heapSort", heapSort([1, 4, 2, 7, 5, 1, -1000, 49935, -4, 777, 0, 9, 1, 4, -30, 0, 9, 4]));
console.log("countSort", countSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("bucketSort", bucketSort([1, 4, 2, 7, 5, 1, -1000, 49935, -4, 777, 0, 9, 1, 4, -30, 0, 9, 4]));
console.log("radixSort", radixSort([10, 44, 22, 72, 5989, 100, 30, 99, 498]));